math_physics_problemswikiaorg-20200215-history
The Simplex Method
Problem You know how to make two items out of cloths: aprons and bookbags. Aprons require 2 hours of cutting time and 4 hours of sewing time. Bookbags require 3 hours of cutting time and 3 hours of sewing time. You sell the aprons for $18 and the bookbags for $20. How many of each item should you make if you spend 12 hours cutting and 18 hours sewing? Part 1: Solve using the dictionary method. Part 2: Solve using the tableau method. Solution 'Part 1: Dictionary method' Let a represent aprons and b represent bookbags. The linear programming problem we wish to solve is to maximize the revenue (objective function) 18a + 20b subject to the cutting time constraint 2a + 3b \le 12 and the sewing time constraint 4a + 3b \le 18 . : \begin{align} Max \quad 18a + 20b \\ 2a + 3b \le 12 \\ 4a + 3b \le 18 \\ a, b \ge 0 \end{align} Step 1: Constructing a dictionary Introduce the slack variables for the number of constraints and construct a dictionary. Dictionary 1 : \begin{align} Z &= 0 + 18a + 20b \\ s_1 &= 12 - 2a - 3b \\ s_2 &= 18 - 4a - 3b \end{align} Note that throughout the entire process a, b, s_1, s_2 \ge 0 . The basic solution is determined by setting the variables in the objective function equal to zero and reading the constant terms for each variable in the dictionary. Basic solution : (a,b,s_1,s_2) = (0,0,12,18) Objective value : Z = 0 Step 2: Pivoting process 1) Selecting the entering variable. The variable b is the entering variable since its coefficient, 20, is the largest non-negative coefficient in the objective function. 2) Find the tightest constraint by comparing which ratio is lowest. For s_1 : 12/3 = 4 For s_2 : 18/3 = 6 The ratio for s_1 is smaller than the ratio for s_2 , thus s_1 is the leaving variable. 3) Calculate via swapping and substitution. : \begin{align} Z &= 0 + 18a + 20(4 - (2/3)a - (1/3)b) \\ b &= 4 - (2/3)a - (1/3)b \\ s_2 &= 18 - 4a - 3(4 - (2/3)a - (1/3)b) \end{align} Dictionary 2 : \begin{align} Z &= 80 + (14/3)a - (20/3)s_1 \\ b &= 4 - (2/3)a - (1/3)b \\ s_2 &= 6 - 2a + s_1 \end{align} Basic solution : (a,b,s_1,s_2) = (0,4,0,6) Objective value : Z = 80 The coefficient of variable a is positive, so there is a more optimal solution. 1) The variable a is the entering variable. 2) The variable s_2 is the leaving variable. For b : 4/(2/3) = 6 For s_2 : 6/2 = 3 : \begin{align} Z &= 80 + (14/3)(3 - (1/2)s_2 + (1/2)s_1) - (20/3)s_1 \\ b &= 4 - (2/3)(3 - (1/2)s_2 + (1/2)s_1) - (1/3)b \\ a &= 3 - (1/2)s_2 + (1/2)s_1 \end{align} Dictionary 3 : \begin{align} Z &= 94 - (13/3)s_1 - (7/3)s_2 \\ b &= 2 - (2/3)s_1 + (1/3)s_2 \\ a &= 3 + (1/2)s_1 - (1/2)s_2 \end{align} Notice the coefficients in the objective function are negative; hence, the pivoting process ends here because the objective function cannot be increased any further. Basic solution : (a,b,s_1,s_2) = (3,2,0,0) Objective value : Z = 94 Therefore you should make 3 aprons and 2 bookbags. The maximum revenue is $94. 'Part 2: Tableau Method' Tableau 1 Select the column with the most negative entry in row 3. This is column 2 (y enters). Divide the rightmost entry with their respective entries in column 2. : 12/3 = 4 : 18/3 = 6 Select the row with the lower quotient in column 2. This is row 1 (s1 leaves). Row reduce to make the other entries of column 2 zero. : R_2 - R_1 : R_3 + (20/3)R_1 Tableau 2 Select the column with the most negative entry in row 3. This is column 1 (x enters). Divide the rightmost entry with their respective entries in column 1. : 12/2 = 6 : 6/2 = 3 Select the row with the lower quotient in column 1. This is row 2 (s2 leaves). Row reduce to make the other entries of column 1 zero. : R_1 - R_2 : R_3 + (7/3)R_2 Tableau 3 No more negative entries in row 3! Done! Solution : (x, y) = (6/2, 6/3) = (3, 2) : Z = 94/1 = 94 Category:Linear algebra Category:Linear programming